package leetcode;

import java.util.Stack;

/**
 * 42. 接雨水  https://leetcode.cn/problems/trapping-rain-water/description/
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class LeetCode42 {

    public static int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        int ans = 0;
        while (index < height.length) {
            while (!stack.isEmpty() && height[stack.peek()] < height[index]) {
                Integer pop = stack.pop();
                if(stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int h = Math.min(height[left], height[index]) - height[pop];
                int w = index - left - 1;
                ans = ans + h * w;

            }
            stack.push(index++);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }
}